We investigate the problem of preselecting a subset of buyers (also called agents) participating in a market so as to optimize the performance of stable outcomes. We consider four scenarios arising from the combination of two stability notions, namely market envy-freeness and agent envy-freeness, with the two state-of-the-art objective functions of social welfare and seller’s revenue. When insisting on market envy-freeness, we prove that the problem cannot be approximated within n 1−ε (with n being the number of buyers) for any ε > 0, under both objective functions; we also provide approximation algorithms with an approximation ratio tight up to subpolynomial multiplicative factors for social welfare and the seller’s revenue. The negative result, in particular, holds even for markets with single-minded buyers. We also prove that maximizing the seller’s revenue is NP-hard even for a single buyer, thus closing a previous open question. Under agent envy-freeness and for both objective functions, instead, we design a polynomial time algorithm transforming any stable outcome for a market involving any subset of buyers into a stable outcome for the whole market without worsening its performance. This result creates an interesting middle-ground situation where, if on the one hand buyer preselection cannot improve the performance of agent envy-free outcomes, on the other one it can be used as a tool for simplifying the combinatorial structure of the buyers’ valuation functions in a given market. Finally, we consider the restricted case of multi-unit markets, where all items are of the same type and are assigned the same price. For these markets, we show that preselection may improve the performance of stable outcomes in all of the four considered scenarios, and design corresponding approximation algorithms.

Pricing-based mechanisms have been widely studied and developed for resource allocation in multi-agent systems. One of the main goals in such studies is to avoid envy between the agents, i.e., guarantee fair allocation. However, even the simplest combinatorial cases of this problem is not well understood. Here, we try to fill these gaps and design polynomial revenue maximizing pricing mechanisms to allocate homogeneous resources among buyers in envy-free manner. In particular, we consider envy-free outcomes in which all buyers' utilities are maximized. We also consider pair envy-free outcomes in which all buyers prefer their allocations to the allocations obtained by other agents. For both notions of envy-freeness, we consider item and bundle pricing schemes. Our results clearly demonstrate the limitations and advantages in terms of revenue between these two different notions of envy-freeness.

We study the problem of designing envy-free sponsored search auctions, where bidders are budget-constrained. Our primary goal is to design auctions that maximize social welfare and revenue — two classical objectives in auction theory. For this purpose, we characterize envy-freeness with budgets by proving several elementary properties including consistency, monotonicity and transitivity. Based on this characterization, we come up with an envy-free auction, that is both social-optimal and bidder-optimal for a wide class of bidder types. More generally, for all bidder types, we provide two polynomial time approximation schemes (PTASs) for maximizing social welfare or revenue, where the notion of envy-freeness has been relaxed slightly. Finally, in cases where randomization is allowed in designing auctions, we devise similar PTASs for social welfare or revenue maximization problems.

Pricing-based mechanisms have been widely studied and developed for resource allocation in multi-agent systems. One of the main goals in such studies is to avoid envy between the agents, i.e., guarantee fair allocation. However, even the simplest combinatorial cases of this problem is not well understood. Here, we try to fill these gaps and design polynomial revenue maximizing pricing mechanisms to allocate homogeneous resources among buyers in envy-free manner. In particular, we consider envy-free outcomes in which all buyers' utilities are maximized. We also consider pair envy-free outcomes in which all buyers prefer their allocations to the allocations obtained by other agents. For both notions of envy-freeness, we consider item and bundle pricing schemes. Our results clearly demonstrate the limitations and advantages in terms of revenue between these two different notions of envy-freeness.